//
// Description: 153. 寻找旋转排序数组中的最小值
// Created by Loading on 2021/4/8.
//

#include <bits/stdc++.h>

using namespace std;

int findMin(vector<int> &nums) {
    int n = nums.size();
    if (n == 1) {
        return nums[0];
    }

    int l = 0, r = n - 1;
    while (l < r) {
        /* 虽然题目给出了数据范围保证了 l + r 不可能越界，但仍要注意，最好使用 l + (r - l) / 2 的方式 */
        //int mid = (l + r) / 2;
        int mid = l + (r - l) / 2;
        if (nums[mid] < nums[r]) {//若中间值小于最右侧值，则最小值出现在中间及其左侧，右侧舍弃
            r = mid;
        } else {//若中间值大于最右侧值，则最小值出现在中间值的右侧，左侧舍弃
            l = mid + 1;
        }
    }

    //最终 l 和 r 都将指向最小值
    return nums[l];
}

int main() {
    vector<int> nums = {18, 11, 13, 15, 17};
    cout << findMin(nums) << endl;
}